"""
动态规划 - 存储当前运算结果，后续运算只与当前结果相关
"""
from functools import lru_cache


@lru_cache()
def fib(num):
    if num == 0:
        return 0
    elif num == 1:
        return 1
    return fib(num - 1) + fib(num - 2)


# for num in range(120):
#     print(f'{num}: {fib(num)}')


def sub_max_sum1(items):
    """子列表最大和（方法1）"""
    current_max = items[0]
    for index, item in enumerate(items):
        total = item
        if total > current_max:
            current_max = total
        for value in items[index + 1:]:
            total += value
            if total > current_max:
                current_max = total
    return current_max


def sub_max_sum2(items):
    """子列表最大和（方法2）"""
    cur = [items[0], ]
    all = [items[0], ]
    for i in range(1, len(items)):
        cur.append(max(items[i], cur[i - 1] + items[i]))
        all.append(max(all[i - 1], cur[i]))
    return all[-1]


print(sub_max_sum2([1, -2, 3, 5, -3, 2]))
print(sub_max_sum2([0, -2, 3, 5, -1, 2]))
print(sub_max_sum2([-9, -2, -3, -5, -3]))
